﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0102_MaxPoints : IAlgorithm
    {
        // 149. 直线上最多的点数

        // 给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

        // 提示：
        //  1 <= points.length <= 300
        //  points[i].length == 2
        //  -10^4 <= xi, yi <= 10^4
        //  points 中的所有点 互不相同

        public void Test()
        {
            //[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]
            // 算法参数定义
            var points = new int[][] { new int[] { 1, 1 }, new int[] {3,2 },
                new int[] {5,3 }, new int[] { 4,1 }, new int[] { 2, 3 }, new int[] { 1, 4 } };
            // 算法执行与打印
            Console.WriteLine(MaxPoints(points));
        }

        // 算法
        public int MaxPoints(int[][] points)
        {
            int n = points.Length;
            int ans = 1;
            for (int i = 0; i < n; i++)
            {
                int[] x = points[i];
                for (int j = i + 1; j < n; j++)
                {
                    int[] y = points[j];
                    int cnt = 2;
                    for (int k = j + 1; k < n; k++)
                    {
                        int[] p = points[k];
                        int s1 = (y[1] - x[1]) * (p[0] - y[0]);
                        int s2 = (p[1] - y[1]) * (y[0] - x[0]);
                        if (s1 == s2) cnt++;
                    }
                    ans = Math.Max(ans, cnt);
                }
            }
            return ans;
        }
    }
}
